package demo1;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-08-04
 * Time: 15:10
 */
public class QuickSort {

    /**
     * 快速排序
     * 时间复杂度 : O(N * logN), 每层有 N 个数要排, 分治分组的高度为 logN
     * 空间复杂度 : O(logN) 当左边递归完了回收, 右边接着递归
     * 不稳定排序
     *
     * @param array 排序数组
     * @param start 分治数组的左边界
     * @param end   分治数组的右边界
     */
    public static void quickSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }

        // 在递归数组较小, 并且越来越有序时采用直接插入排序提升排序速度
        // 表示数组有 (1 , 7] 个元素以内
        if (end - start + 1 <= 7) {
            insertSort(array, start, end);
        }

        // 进行分组递归之前, 提前去找到基准元素, 然后进行调整在进行快排
        // 让数组划分得结果更加的均匀
        int index = findMidOfThreeNum(array, start, end);

        // 寻找基准元素
        int pivot = partitionDigHole(array, start, end);

        // 递归基准元素左边
        quickSort(array, start, pivot - 1);

        // 递归基准元素右边
        quickSort(array, pivot + 1, end);

    }

    /**
     * 直接插入排序, 对递归小数组进行插入排序优化, 让原本已经趋近有序的数组更快排序
     *
     * @param array 递归排序的小数组
     * @param left  数组的左边界
     * @param right 数组的右边界
     */
    private static void insertSort(int[] array, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int tmp = array[i];
            int j = i - 1;
            for (; j >= left; j--) {
                if (array[j] > tmp) {
                    array[j + 1] = array[j];
                } else {
                    break;
                }
            }
            array[j + 1] = tmp;
        }
    }

    /**
     * 三数取中法 : 提前对基准元素进行选取, 并调整到 left 位置, 让分治数组划分更加均匀
     *
     * @param array 排序数组
     * @param start 数组左边界
     * @param end   右边界
     * @return 返回新的基准元素
     */
    private static int findMidOfThreeNum(int[] array, int start, int end) {
        int midIndex = start + ((end - start) >> 1);

        if (array[start] < array[end]) {
            // 3  X   9
            if (array[midIndex] < array[start]) {
                return start;
            } else if (array[midIndex] > array[end]) {
                return end;
            } else {
                return midIndex;
            }

        }
        // 9  X   3
        else {
            if (array[midIndex] > array[start]) {
                return start;
            } else if (array[midIndex] < array[end]) {
                return end;
            } else {
                return midIndex;
            }
        }
    }

    /**
     * Hoare 法寻找基准元素
     *
     * @param array 找基准排序数组
     * @param left  传入数组的左边界
     * @param right 传入数组的有边界
     * @return 返回新的基准
     */
    private static int partitionHoare(int[] array, int left, int right) {
        int i = left;

        // 均以传入数组的左边界为初始基准
        int pivot = array[left];

        while (left < right) {

            // 先右边寻找比基准小的数
            while (left < right && array[right] >= pivot) {
                right--;
            }

            // 在左边寻找比基准大的数
            while (left < right && array[left] <= pivot) {
                left++;
            }

            swap(array, left, right);
        }

        // 将这个初始基准元素放到中间, 以此为界划分数组
        swap(array, i, left);

        // 返回基准下标
        return left;
    }

    /**
     * 挖坑法寻找基准元素
     *
     * @param array 寻找基准元素的数组
     * @param left  数组左边界
     * @param right 数组右边界
     * @return 返回新基准元素下标
     */
    public static int partitionDigHole(int[] array, int left, int right) {

        int pivot = array[left]; // 初始坑位

        while (left < right) {

            // 先从右边开始寻找比初始基准小的数
            while (left < right && array[right] >= pivot) {
                right--;
            }

            // 填入坑位
            array[left] = array[right];

            // 然后从右边开始寻找比基准大的数
            while (left < right && array[left] <= pivot) {
                left++;
            }

            array[right] = array[left];
        }

        // 结束后将初始坑位的值填入到现存坑位
        array[left] = pivot;

        return left;
    }


    private static void swap(int[] array, int left, int right) {
        int tmp = array[left];
        array[left] = array[right];
        array[right] = tmp;
    }

    public static void main(String[] args) {
        int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        QuickSort.quickSort(array, 0, array.length - 1);
        System.out.println(Arrays.toString(array));
    }
}
